def shell_sort(nums: list[int]):
    """希尔排序"""  # 开始时先使用比较大的步子排序使序列“基本有序”，最后再使用插入排序
    n = len(nums)

    # 获取间隔序列
    h = 1
    while h < n // 3:
        h = h * 3 + 1

    while h > 0:
        for i in range(h, n):
            base = nums[i]
            j = i - h
            while j >= 0 and nums[j] > base:
                nums[j + h] = nums[j]
                j -= h
            nums[j + h] = base
        h = (h - 1) // 3


if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2, 9, 8, 6, 7]
    shell_sort(nums)
    print("排序完成后 nums =", nums)
    # 排序完成后 nums = [1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
